from hazard_value.shuffle_edges import *
from hazard_value.helpers import *
from hazard_value.nfa import *
from decimal import *
import numpy
import sys

# strategically compute the connectivity weight 
def compute_hazard_value_strategical  (g, D, W, nfa, k, phi, p) :

	# setup the sets of failed links
	used_edges = dict()
	E = set()
	oracle = dict()

	change_points = compute_change_points(g, nfa)
	incidents = dict()

	for q in change_points:
		for w in change_points[q]: incidents[w] = set(g.incident(w, mode="in"))

	distances = numpy.array(g.shortest_paths())

	for X in D:
		for s, t in X: 
			edges = compute_nfa_used_edges (g, s, t, nfa, oracle)
			used_edges[s, t] = edges
			for q in used_edges[s, t]: 
				E |= used_edges[s, t][q]

	if len(E)==0: return 0, 0.0, 0.0, 1
	max_k = min(k, len(E))

	coefficients = compute_binomial_coefficients (len(E))
	probabilities = compute_probabilities(phi, E, len(E))

	weight = Decimal("0.0")
	optimum = Decimal("0.0")
	scenarios = 0
	active_cuts = dict()
	weights = dict()

	# setup a new demand
	def setup_new_demand (stack, demands):
		if len(demands)==0: return False
		s, t = demands.pop()
		stack.append((s, t))
		return True

	# backtracking function
	def backtrack (stack, edges, F, U, demands):

	# remove the top most demand on the stack while it has no active run anymore
		while len(stack)>0:
			s, t = stack[-1]
			if len(active_cuts[s, t])==0:
				stack.pop()
				demands.append((s, t))
				continue

			# finally try to update the active capacity of the edges of the active cut

			cut = active_cuts[s, t][-1]
			index = len(cut)-1
			while index>=0 and g.es[cut[index]]["capacity"]>0:
				g.es[cut[index]]["capacity"] = 0
				F.add(cut[index])
				U.remove(cut[index])
				index -= 1
			# if we found an edge that was already failed set it to up
			if index>=0:
				F.remove(cut[index])
				U.add(cut[index])
				g.es[cut[index]]["capacity"] = sys.maxsize
				return
			# otherwise remove the cut from the stack
			else:
				active_cuts[s, t].pop()
				for e in cut:
					g.es[e]["capacity"] = 1
					F.remove(e)
					edges.add(e)

	# compute the reward for each demand X in D
	for X in D:
		demands = list(X)
		demands.sort(key=lambda x: W[x])
		edges = set()

		# init the active stacks for all flows in X
		for s, t in X:
			active_cuts[s, t] = list()
			for q in used_edges[s, t]: 
				edges |= used_edges[s, t][q]

		# init the stack and all its dependencies
		weights[X] = Decimal("0.0")
		for e in range(len(g.es)): g.es[e]["capacity"] = 1 if e in edges else 0
		complement = E - edges
		stack = list()
		setup_new_demand(stack, demands)

		F = set()
		U = set()
		reachable_max = max([W[s, t] for s, t in X])
		optimum += reachable_max
		unused_edges = set(edges)

		# while the stack is not empty try to fail the top most pair on the stack
		while len(stack)>0:
			s, t = stack[-1]
			maxflow = g.maxflow(s, t, capacity="capacity")
			scenarios += 1
			# if the demand cannot be disconnected compute the corresponding reward and backtrack
			if len(F)+maxflow.value>max_k:
					n = len(complement)+len(edges)
					cmp = compute_complement_weight(coefficients, probabilities, n, F, k)
					weight += W[s, t] * cmp
					weights[X] += W[s, t]*cmp
					backtrack (stack, edges, F, U, demands)
			# otherwise disconnect the demand and stack the next available one if possible
			else:
				if maxflow.value==0 and len(active_cuts[s, t])>0:
					backtrack (stack, edges, F, U, demands)
					continue
				elif maxflow.value>0:

					cut = list((set(maxflow.cut) & edges)-(F|U))
					for e in cut: 
						g.es[e]["capacity"] = 0
						F.add(e)
						edges.remove(e)
					active_cuts[s, t].append(cut)
				unused_edges -= F
				# add a new demand to the stack if it is possible, otherwise backtrack
				if not setup_new_demand(stack, demands):
					backtrack (stack, edges, F, U, demands)

	optimum *= sum([coefficients[-1][i]*probabilities[i] for i in range(len(E))])
	return scenarios, weight, optimum, 1-weight/optimum